Aligning protein-protein interaction (PPI) networks of different species hasdrawn a considerable interest recently. This problem is important toinvestigate evolutionary conserved pathways or protein complexes acrossspecies, and to help in the identification of functional orthologs through thedetection of conserved interactions. It is however a difficult combinatorialproblem, for which only heuristic methods have been proposed so far. Wereformulate the PPI alignment as a graph matching problem, and investigate howstate-of-the-art graph matching algorithms can be used for that purpose. Wedifferentiate between two alignment problems, depending on whether strictconstraints on protein matches are given, based on sequence similarity, orwhether the goal is instead to find an optimal compromise between sequencesimilarity and interaction conservation in the alignment. We propose newmethods for both cases, and assess their performance on the alignment of theyeast and fly PPI networks. The new methods consistently outperformstate-of-the-art algorithms, retrieving in particular 78% more conservedinteractions than IsoRank for a given level of sequence similarity.Availability:http://cbio.ensmp.fr/proj/graphm\_ppi/, additional data and codesare available upon request. Contact: jean-philippe.vert@mines-paristech.fr
展开▼
